﻿// BFS.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

void BFS_path(int start_x, int start_y, int &finish_x, int &finish_y,int height,int maze[WIDTH][LENGTH][HEIGHT]) 
{
    struct queue//数组队列
    {
        int x, y, s, f;//s:步数，f:上一节点下标
    }node[2500];

    int flag[WIDTH][LENGTH];//标记已走过的点
    int head = 1, tail = 1;//队列头指针尾指针
    int cot_x, cot_y;//试探点
    bool action=false;//表示是否到达终点来结束循环
    //初始化
    for (int i = 0; i < WIDTH; i++)
    {
        for (int j = 0; j < LENGTH; j++)
        {
            flag[i][j] = 0;
        }
    }

    flag[start_x][start_y] = 1;//走过设1
    node[tail].x = start_x;
    node[tail].y = start_y;
    node[tail].s = 0;
    node[tail].f = 0;
    tail++;

    //寻路
    while (head < tail)//队列为空或者到达终点结束循环
    {
        //判断方向
        for (int direction = 0; direction < 4; direction++)//遍历四个方向
        {
            switch (direction)
            {
            case 0://右
                cot_x = node[head].x + 1;
                cot_y = node[head].y;
                break;
            case 1://下
                cot_x = node[head].x;
                cot_y = node[head].y + 1;
                break;
            case 2://左
                cot_x = node[head].x - 1;
                cot_y = node[head].y;
                break;
            case 3://下
                cot_x = node[head].x;
                cot_y = node[head].y - 1;
                break;
            }
            if (cot_x<0 || cot_y<0 || cot_x>LENGTH - 1 || cot_y>WIDTH - 1)//越界
                continue;
            if (maze[cot_y][cot_x][height] == 0 && flag[cot_y][cot_x] == 0)//没走过且没撞墙
            {
                node[tail].s = node[head].s + 1;
                node[tail].f = head;
                node[tail].x = cot_x;
                node[tail].y = cot_y;
                flag[cot_y][cot_x] = 1;
                tail++;
            }
            if (cot_x == finish_x && cot_y == finish_y)//到达终点
            {
                action = true;
                break;
            }
        }
        if (action == true)//action==true表示到达终点
            break;
        //四个方向遍历结束
        head++;
    }
    int step = tail - 2;
    finish_x = node[step].x;
    finish_y = node[step].y;
}